package com.ting.test.algorithms.滑动窗口;

import java.util.Stack;

/**
 * 给定一个有序数组arr，代表坐落在X轴上的点
 * <p>
 * 给定一个正数K，代表绳子的长度
 * <p>
 * 返回绳子最多压中几个点？
 * <p>
 * 即使绳子边缘处盖住点也算盖住
 * <p>
 * 可以认为是一个固定窗口大小的问题
 */
public class 绳子最多压中几个点 {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 6, 9, 12, 15, 16, 18, 20};
        int count = f2(arr, 8);
        System.out.println("count=" + count);
    }

    private static int f2(int[] arr, int K) {
        int L = 0, R = 0;
        int N = arr.length;
        int max = 0;
        //先固定L
        while (L < N) {
            while (R < N && (arr[R] - arr[L] <= K)) {
                R++;
            }
            max = Math.max(max, R - L);
            L++;
        }
        return max;
    }
}
